package org.example.leetcode;

import java.util.TreeMap;

/**
 * 假设你有一个数组fundPrices，长度为n，其中fund_prices[n]是基金在第n天的价格，请根据这个价格数组，返回买卖基金能获得的最大收益，
 * 你总共只能买入一次和卖出一次，且买入必须在卖出之前。如果没有收益，请返回0（假设买入卖出均无手续费）
 * 数据范围：0 <= n <= 10000;  0 <= price <=1000;
 * 要求：空间复杂度O(1)O(1)，时间复杂度O(n)O(n)
 * 示例：
 * 输入：[3,2,7,10,5,2,9]
 * 返回值：8
 * 说明：
 * 在第2天(价格 = 2)的时候买入，在第4天(价格 = 10)的时候卖出，最大利润 = 10-2 = 8;
 * @author shenguangyang
 */
public class MaxProfit {
    public int getMaxProfit(int[] fundPrices) {
        if (fundPrices == null || fundPrices.length <= 1) {
            return 0;
        }
        int result = 0;
        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(fundPrices[0], fundPrices[0]);

        for (int i = 0; i < fundPrices.length - 1; i++) {
            int min = map.firstKey();
            int next = fundPrices[i + 1];
            if (min < next) {
                int tmp = next - min;
                result = Math.max(tmp, result);
            }
            map.put(next, next);
        }

        return result;
    }

    public static void main(String[] args) {
        MaxProfit maxProfit = new MaxProfit();
        // int[] fundPrices = {3,2,7,10,5,2,9};
        int[] fundPrices = {3, 2, 1, 5, 20, 7, 10, 5, 2, 9};
        System.out.println(maxProfit.getMaxProfit(fundPrices));
    }
}
